import java.util.*;

public class Leetcode {
}

//leetcode:1576:替换所有的问号
class Solution1 {
    public String modifyString(String s) {
       char[] ss = s.toCharArray();
       for(int i = 0;i < ss.length ;i++){
           if(ss[i] == '?'){
               for(char ch = 'a';ch <= 'z';ch++){
                    if((i == 0 || ss[i-1] != ch )&& (i == ss.length-1 || ss[i+1] != ch)){
                        ss[i] = ch;
                        break;
                    }
               }
           }
       }
       return String.valueOf(ss);
    }
}

//leetcode：128:最长连续序列
class Solution2 {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x : nums){
            set.add(x);
        }
        int ret = 0;
        for(int y : set){
            if(!set.contains(y-1)){
                int num = y;
                int k = 1;
                while(set.contains(num+1)){
                    k++;
                    num++;
                }
                ret = Math.max(ret,k);
            }
        }
        return ret;
    }
}

//leetcode:287：寻找重复数
class Solution3 {
    public int findDuplicate(int[] nums) {
        int fast = 0,slow = 0;
        //快慢指针法：找环
        //从0下标开始，根据此时数组的值去得到下一个要去的位置，再得到值作为下一个要求的位置。。。
        //如果我们存在重复的元素，那么我们这两重复元素要去的下一个位置一定是相同的
        //这样我们发现他就形成了一个闭环
        do{
            fast = nums[nums[fast]];
            slow = nums[slow];
        }while(fast != slow);
        //当我们确定了他是一个闭环后，我们再将慢指针指向开始位置，让快慢指针一起走，直到他们的值相同
        //由于slow = nums[slow];此时的slow就是重复的元素
        slow = 0;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
}

//leetcode:49：字母异位词分组
class Solution4 {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String str : strs){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            List<String> list = map.getOrDefault(key,new ArrayList<String>());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}